#include "main/utils.h"
#include "lib/list.h"
using namespace std;

class Solution {
  ListNode* front_node;
  public:
  bool isPalindrome(ListNode* head) {
    vector<int> vec;
    while (head) {
      vec.push_back(head->value);
      head = head->next;
    }
    int len = vec.size();
    for (int i = 0; i < len; ++i) {
      if (vec[i] != vec[len - i - 1]) {
        return false;
      }
    }
    return true;
  }

  bool pal_check(ListNode* node) {
    if (node) {
      if (!pal_check(node->next)) {
        return false;
      }
      if (front_node->value != node->value) {
        return false;
      }
      front_node = front_node->next;
    }
    return true;
  }

  bool isPalindrome1(ListNode* head) {
    front_node = head;
    return pal_check(front_node);
  }
};

int main() {
  vector<int> node_vals = {1, 2, 2, 1};
  ListNode* phead = CreateList(node_vals);
  Solution su;
  cout << su.isPalindrome(phead) << endl;

  ListNode* phead1 = CreateList(node_vals);
  cout << su.isPalindrome1(phead1) << endl;

  return 0;
}
